package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ16_区间连接器 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/16.txt"));
        MyUtil.START();
        Solution(in);
//        Solution2(in);
        MyUtil.END();
    }

    static void Solution(Scanner in) {
        String[] sArray = in.nextLine().replaceAll("\\[", "").replaceAll("]", "").split(",");
        String[] lianjie = in.nextLine().replaceAll("\\[", "").replaceAll("]", "").split(",");
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < sArray.length; i += 2) {
            int a = Integer.parseInt(sArray[i]);
            int b = Integer.parseInt(sArray[i + 1]);
            list.add(new int[]{a, b});
        }
        list.sort((a, b) -> {
            return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
        });
        int[] firstQujian = list.get(0);
        int left = firstQujian[0];
        int right = firstQujian[1];
        int maxRight = right;
        List<int[]> newList = new ArrayList<>();
        for (int i = 1; i < list.size(); i++) {
            int[] now = list.get(i);
            if (now[0] > right) {
                if (maxRight > right) {
                    right = maxRight;
                }
                if (now[0] > maxRight) {
                    newList.add(new int[]{left, maxRight});
                    left = now[0];
                    right = now[1];
                    maxRight = right;
                }
            }
            maxRight = Math.max(maxRight, now[1]);
        }
        if (maxRight >= right) {
            newList.add(new int[]{left, maxRight});
        }

        int[] lianjieqi = new int[lianjie.length];
        for (int i = 0; i < lianjie.length; i++) {
            lianjieqi[i] = Integer.parseInt(lianjie[i]);
        }
        Arrays.sort(lianjieqi);
        int res = newList.size() - 1;
        for (int i = 1; i < newList.size(); i++) { //注意 i < newList.size()，而不是 i < res 因为 res 是动态变化的。
            int need = Math.abs(newList.get(i)[0] - newList.get(i - 1)[1]);
            for (int j = 0; j < lianjieqi.length; j++) {
                if (lianjieqi[j] >= need) {
                    lianjieqi[j] = 0;
                    res--;
                    break;
                }
            }
        }
        System.out.println(res + 1);
    }

    static void Solution2(Scanner in) {
        String regionsStr = in.nextLine();
        String linksStr = in.nextLine();

        List<int[]> regions = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(regionsStr, ",[]");
        while (st.hasMoreTokens()) {
            int lo = Integer.parseInt(st.nextToken());
            int hi = Integer.parseInt(st.nextToken());
            regions.add(new int[]{lo, hi});
        }
        List<Integer> links = new ArrayList<>();
        st = new StringTokenizer(linksStr, ",[]");
        while (st.hasMoreTokens()) {
            int link = Integer.parseInt(st.nextToken());
            links.add(link);
        }

        regions.sort((a, b) -> {
            return a[0] > b[0] ? 1 : a[0] < b[0] ? -1 : 0;
        });
        int[] region = null;
        Iterator<int[]> iter = regions.iterator();
        while (iter.hasNext()) {
            int[] next = iter.next();
            if (region == null) {
                region = next;
            } else if (region[1] >= next[0]) {
                if (region[1] < next[1]) {
                    region[1] = next[1];
                }
                iter.remove();
            } else {
                region = next;
            }
        }

        List<Integer> gaps = new ArrayList<>();
        iter = regions.iterator();
        region = null;
        while (iter.hasNext()) {
            int[] next = iter.next();
            if (region != null) {
                int gap = next[0] - region[1];
                gaps.add(gap);
            }
            region = next;
        }
        Collections.sort(gaps);
        Collections.sort(links);

        int i = 0; // gaps index
        int j = 0; // links index
        while (i < gaps.size() && j < links.size()) {
            if (links.get(j) >= gaps.get(i)) {
                gaps.set(i, 0);
                i++;
                j++;
            } else {
                j++;
            }
        }
        int noneZoreNum = 0;
        for (int g : gaps) {
            if (g > 0) {
                noneZoreNum++;
            }
        }
        ;
        System.out.println(noneZoreNum + 1);
    }
}
